package com.banzhang.sort;

import java.util.Arrays;

public class MySort {
    public static void main(String[] args) {
        int[] R = {0, 56, 45, 154, 356, 2, 42, 64, 21, 1};
        int n = 9;
        // DInsertSort(R,n);
        //  System.out.println("-----------------------");
        //  BinsertSort(R,n);
        // ShellSort(R,n);
        // BinsertSort(R,n);
        //bubble_sort_Upgrade(R,n);
        SelectSort(R, n);
    }

    static void SelectSort(int[] R, int n) {
        for (int i = 1; i < n; i++) {
            int k = i;
            for (int j = i + 1; j <= n; j++) {
                if (R[j] < R[k])
                    k = j;//记录最小值位置
            }
            if (k != i) {
                int temp;
                temp = R[i];
                R[i] = R[k];
                R[k] = temp;
            }
        }
        System.out.println("选择排序的结果:");
        for (int i = 1; i <= n; i++) {
            System.out.println(R[i]);
        }
    }

    static void ShellSort(int[] R, int n) {
        int gap = n / 2;
        while (gap >= 1) {
            for (int i = 1 + gap; i <= n; i += gap) {
                if (R[i] < R[i - gap]) {
                    R[0] = R[i];
                    int j = i - gap;
                    for (; j > 0 && R[0] < R[j]; j -= gap) {
                        R[j + gap] = R[j];
                    }
                    R[j + gap] = R[0];
                }
            }
            gap /= 2;
        }
        System.out.println("希尔排序的结果:");
        for (int i = 1; i <= n; i++) {
            System.out.println(R[i]);
        }
    }

    static void DInsertSort(int[] R, int n) {
        for (int i = 2; i <= n; i++) {
            if (R[i] < R[i - 1]) {
                R[0] = R[i];
                int j = i - 1;
                for (; R[0] < R[j]; j--) {
                    R[j + 1] = R[j];
                }
                R[j + 1] = R[0];
            }
        }
        System.out.println("直接插入排序的结果:");
        for (int i = 1; i <= n; i++) {
            System.out.println(R[i]);
        }
    }

    static void BinsertSort(int[] R, int n) {
        for (int i = 2; i <= n; i++) {
            R[0] = R[i];
            int low = 1;
            int high = i - 1;
            int mid;
            while (low <= high) {
                mid = (low + high) / 2;
                if (R[0] < R[mid])
                    high = mid - 1;
                else low = mid + 1;
            }
            for (int j = i - 1; j >= high + 1; --j) {
                R[j + 1] = R[j];
            }
            R[high + 1] = R[0];
        }
        System.out.println("折半插入排序的结果:");
        for (int k = 1; k <= n; k++) {
            System.out.println(R[k]);
        }
    }

    static void bubble_sort(int[] R, int n) {
        int i, j, temp;
        for (i = 1; i <= n - 1; i++) {
            for (j = 1; j <= n - i; j++) {
                if (R[j] > R[j + 1]) {
                    temp = R[j];
                    R[j] = R[j + 1];
                    R[j + 1] = temp;
                }
            }
        }
        System.out.println("冒泡排序的结果:");
        for (int k = 1; k <= n; k++) {
            System.out.println(R[k]);
        }
    }


    static void bubble_sort_Upgrade(int[] R, int n) {
        int i, j, temp;
        int flag = 1;
        for (i = 1; i <= n - 1 && flag == 1; i++) {
            flag = 0;
            for (j = 1; j <= n - i; j++) {
                if (R[j] > R[j + 1]) {
                    flag = 1;
                    temp = R[j];
                    R[j] = R[j + 1];
                    R[j + 1] = temp;
                }
            }
        }
        System.out.println("冒泡排序的结果:");
        for (int k = 1; k <= n; k++) {
            System.out.println(R[k]);
        }
    }
}
